package _interview100;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 */
public class No416 {
    private int[] nums;

    public boolean canPartition1(int[] nums) {
        this.nums = nums;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;

        return dfs(nums.length - 1, sum / 2);
    }

    private boolean dfs(int i, int c) {
        if (i < 0) return c == 0;
        else if (nums[i] > c) return dfs(i - 1, c);
        else return dfs(i - 1, c) || dfs(i - 1, c - nums[i]);
    }

    public boolean canPartition4(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false;

        boolean[] f = new boolean[sum / 2 + 1];
        f[0] = true;
        for (int num : nums) {
            for (int c = sum / 2; c >= num; c--) {
                f[c] = f[c] || f[c - num];
            }
        }

        return f[sum / 2];
    }
}
